package org.example.lc;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class p53_2 {
    /**
     *
     *  分解成子问题，1,(n)
     *  条件是 longest[i+1]+nums[i] vs longest[i+1]
     *
     *
     */
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int[] mem = new int[nums.length];
        // 初始化最后一个
        mem[nums.length-1] = nums[nums.length-1];
        maxSum =nums[nums.length-1];

        for(int i = nums.length-2;i>=0;i-=1) {

            int temp = mem[i+1]+nums[i];
            // 和自身节点比较
            temp = Math.max(temp,nums[i]);

            // 更新当前节点的连续最大值
            mem[i]=temp;

            // 和这个也比较
            maxSum = Math.max(maxSum,temp);

        }
        return maxSum;
    }
    @Test
    public void t1() {
        assertEquals(6, maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
    @Test
    public void t2() {
        assertEquals(1, maxSubArray(new int[]{1}));
    }
    @Test
    public void t4() {
        assertEquals(-1, maxSubArray(new int[]{-1}));
    }
    @Test
    public void t3() {
        assertEquals(1, maxSubArray(new int[]{-2,1}));
    }
    @Test
    public void t5() {
        assertEquals(23, maxSubArray(new int[]{5,4,-1,7,8}));
    }
    @Test
    public void t6() {
        assertEquals(-1, maxSubArray(new int[]{-1,-2}));
    }


}
